package primary.primary0;

import java.util.Deque;
import java.util.LinkedList;

public class S0155最小栈 {
    /**
     * 94,46
     * 单调栈用来维护这种最大/最小值，非常合适。
     * 注意Deque这个接口的使用，用来当栈用非常合适。
     * 感觉啥时候做了类似的题目来着?就是用一个单调栈来做。
     */
    class MinStack {

        private Deque<Integer> stack = new LinkedList<>();
        private Deque<Integer> minStack = new LinkedList<>();

        public MinStack() {

        }

        public void push(int val) {
            stack.push(val);
            // 注意初始化的情况，用兼容空值的比较吧
            if(minStack.peek() != null && val > minStack.peek()){
                return;
            }
            minStack.push(val);
        }

        public void pop() {
            int popedVal = stack.pop();
            if(popedVal == minStack.peek()){
                minStack.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peekFirst();
        }
    }

    /**
     * 答案
     */
    class MinStack2 {
        Deque<Integer> xStack;
        Deque<Integer> minStack;

        public MinStack2() {
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }

        public void pop() {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

}
